This invention relates to computer systems for simulating physical processes, e.g., fluid flow.
The conventional approach to simulating high Reynolds number flow has been to generate discretized solutions of the Navier-Stokes differential equations, in which high-precision floating point arithmetic operations are performed at each of many discrete spatial locations on variables representing macroscopic physical quantities (e.g., density, temperature, flow velocity). The fastest and most powerful computers available are used, and yet very limited and inexact results have been achieved. To keep run times manageable, very coarse grid resolutions are used, and even at those coarse resolutions there are unacceptable errors in the solutions due to accumulated round off errors inherent in performing successive floating point arithmetic operations.
There has long been an effort to replace the differential equation approach with what is generally known as lattice gas (or cellular) automata, in which the macroscopic-level simulation provided by solving the Navier-Stokes equations is replaced by a microscopic-level model that performs operations on particles moving between sites on a lattice. The goal has long been to find a microscopic-level model of particle interactions and movement that would produce the correct macroscopic results (i.e., variations in density, temperature, etc. as prescribed by the Navier Stokes equations).
The traditional lattice gas simulation assumes a limited number of particles at each lattice site, with the particles being represented by a short vector of bits. Each bit represents a particle moving in a particular direction. For example, one bit in the vector might represent the presence (when set to 1) or absence (when set to 0) of a particle moving along a particular direction. Such a vector might have six bits, with, for example, the values 110000 indicating two particles moving in opposite directions along the X axis, and no particles moving along the Y and Z axes. A set of collision rules governs the behavior of collisions between particles at each site (e.g., a 110000 vector might become a 001100 vector, indicating that a collision between the two particles moving along the X axis produced two particles moving away along the Y axis). The rules are implemented by supplying the state vector to a look-up table that performs a permutation on the bits (e.g., transforming the 110000 to 001100). Particles are then moved to adjoining sites (e.g., the two particles moving along the Y axis would be moved to neighboring sites to the left and right along the Y axis).
Molvig et al. taught an improved lattice gas technique in which, among other things, many more bits were added to the state vector at each lattice site (e.g., 54 bits for subsonic flow) to provide variation in particle energy and movement direction, and collision rules involving subsets of the full state vector were employed. Molvig et al. PCT/US91/04930; Molvig et al., "Removing the Discreteness Artifacts in 3D Lattice-Gas Fluids", Proceedings of the Workshop on Discrete Kinetic Theory, Lattice Gas Dynamics, and Foundations of Hydrodynamics, World Scientific Publishing Co., Pte., Ltd., Singapore (1989); Molvig et al., "Multi-species Lattice-Gas Automata for Realistic Fluid Dynamics", Springer Proceedings in Physics, Vol. 46, Cellular Automata and Modeling of Complex Physical Systems, Springer-Verlag Berlin, Heidelberg (1990) (all hereby incorporated by reference). These improvements and others taught by Molvig et al. produced the first practical lattice gas computer system. Discreteness artifacts that had made earlier lattice gas models inaccurate at modeling fluid flow were eliminated.
Chen et al. taught an improved simulation technique in "Computer System For Simulating Physical Processes", U.S. application No. 08/165,293, filed Dec. 10, 1993 (which is hereby incorporated by reference). Instead of the lattice gas model in which at each lattice site (voxel) there is at most a single particle in any momentum state (e.g., at most a single particle moving in a particular direction with a particular energy), the system used a multi-particle technique in which, at each voxel, multiple particles could exist at each of multiple states (e.g., 0-255 particles could be moving in a particular direction). The state vector, instead of being a set of bits, was a set of integers (e.g., a set of eight bit bytes providing integers in the range of 0 to 255), each of which represented the number of particles in a given state. For example, instead of being limited to a single particle moving in each direction at each momentum state, the system had the flexibility to model multiple particles moving in each direction at each momentum state.
Chen et al.'s use of integer state vectors made possible much greater flexibility in microscopic modeling of physical processes because much more variety was possible in the collision rules that operated on the new integer state vectors. For example, rules were established that collided and scattered a predetermined number of particles while allowing other particles to pass without collision. Integer state vectors also promised to provide solutions to many problems still remaining in single-particle lattice gas techniques even after the improvements taught in the Molvig et al. publications. For example, the multi-particle technique provided a way of achieving the so-called Maxwell-Boltzmann statistics that are characteristic of high Reynolds number fluid flow. The earlier Molvig et al. system achieved so-called Fermi-Dirac statistics, which only resemble Maxwell-Boltzmann statistics if the lattice sites are sparsely populated. The Chen et al. system avoided the need to use a sparsely populated lattice, and thus avoided the huge computational penalty associated therewith.
The Chen et al. system also provided a way of simulating the interaction between fluid particles and solid objects using a new "slip" technique that extended the simulation only to the outer surface of the boundary layer around the solid object, and not through it to the surface of a solid object. At the outer surface of the boundary layer, the collision rules governing interactions between particles and the surface allowed particles to retain tangential momentum. Instead of the particles being returned from the surface in the reverse tangential direction from which they arrived (as occurred with a prior "bounce back" technique), the particles were permitted to reflect from the surface and continue in the same tangential direction in which they arrived.
To simulate physical processes, the Chen et al. system employed collision rules based on a collision operator referred to as the "sandpaper" operator. According to the sandpaper rule, each collision rule was defined as operating on two pairs of momentum states and having a particular "grit", and would transfer a number of elements between a first pair of momentum states and a second pair of momentum states based on likelihood of collisions in each pair of momentum states. For example, if a particular collision rule was defined as having a grit of four and operating on states i, j, k and l, the rule would transfer four particles from each of states i and j to each of states k and l when the likelihood of collisions between elements in states i and j (as determined by the product of the number of elements in states i and j) was greater than the likelihood of collisions between elements in states k and l (as determined by the product of the number of elements in states k and l). Otherwise, the rule would transfer four particles from each of states k and l to each of states i and j.